


#include <iostream>
using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
ListNode(int x) : val(x), next(NULL) {}

};

class Solution
{
public:
    typedef ListNode LNode;
    ListNode* detectCycle(ListNode* head)
    {
        if (nullptr == head)
            return nullptr;

        LNode* meet = HasCircle(head);
        if (meet)
        {
            LNode* beg = head;
            while (beg != meet)
            {
                beg = beg->next;
                meet = meet->next;
            }

            return meet;
        }

        return nullptr;
    }

    ListNode* middleNode(ListNode* head)
    {
        typedef ListNode LNode;

        LNode* fast = head, * slow = head;

        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }

private:
    LNode* HasCircle(LNode* head)
    {
        LNode* slow = head;
        LNode* fast = head;

        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if (fast == slow)
                return slow;
        }

        return nullptr;
    }
};

int main()
{



	return 0;
}